#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> temp;
    int sum = 0;
    void dfs(int k, int n){
        if(temp.size() == k && sum == n){
            ans.emplace_back(temp);
            return;
        }
        else if(sum > n || temp.size()>k) return;
        int i=1;
        if(!temp.empty()) i = temp.back()+1;
        if(n - sum < i) return;
        for( ; i<=9; ++i){
            temp.push_back(i);  sum += i;
            dfs(k, n);
            sum -= i; temp.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        dfs(k, n);
        return ans;
    }
};